[POJ 3204] Ikki's Story I - Road Reconstruction

原题链接:[POJ 3204] Ikki's Story I - Road Reconstruction

#题目大意
给定一个流网络,求图上有多少个边的容量增大以后,最大流也随之增大.只考虑一个边.只需输出数量,不需要输出具体方案.

数据范围:
1n5001 \leq n \leq 500
1m50001 \leq m \leq 5000

思路

对给定的流网络,首先应该把最大流先增广做出来,得到每条边的流量再考虑什么样的边是可以增大同时使得最大流增大的.在做完了之后,显然由于容量的限制,每条边的流量只有两种情况:f(u,v)<c(u,v)f(u,v) < c(u,v)f(u,v)=c(u,v)f(u,v) = c(u,v).分别考虑:
①当f(u,v)<c(u,v)f(u,v) < c(u,v)时,说明这条边没有流满.那么他没有流满的情况要么就是前面的容量不够,要么就是后面的容量不够.因此单纯的增加这条边的容量是没有意义的,因为他本来就没流满,你再给他加容量也不会使情况变好.
②当f(u,v)=c(u,v)f(u,v) = c(u,v)时,说明这条边已经流满了.那么假设说现在给他增大了容量,并且使最大流增大了,说明这条边前后,从源点到这条边,以及这条边往汇点走的路径上,是没有任何一条边流满的.因为你要使最大流增大,就要存在有这样的一条从源点到汇点,并且经过这条流满的边,并且这条流满的边是唯一一个流满的才行.这个时候,这条流满的边就是短板,就是他阻止了最大流的增大.
那很显然一条路径上至少会有一个流满的边,如果没有的话说明增广错误了.既然如此,这个题的方向也就很明确了,先跑一次最大流,再从源点和汇点分别去dfsdfs看能走到哪些点,并且走过的边都是没有流满的,标记一下即可.最后遍历所有的边,如果遍历到一个满边,并且两点各自有标记,那么就说明这条边是题目要找的边.
这里还有一个问题:一个边有两个点,怎么确定谁是汇点应该遍历到的,谁是源点遍历到的?遍历边的时候只取题目给的正向边,不用残量网络里的反向边的话,假设有向边是由uu指向vv的,那么从源点出发,应该要走到这条边上,并且到uu这个点上,就是你是不包含这个边进考虑,那么从源点就要走到uu而不是走到vv.所以各自就是看是不是能从ss走到uu以及能从tt走到vv即可.

代码

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 20000,M = 100000 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N];
int st_t[N],st_s[N];
int q[M],hh,tt;
void add(int u,int v,int w)
{
	edge[idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx++; 
	
	edge[idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx++;
}
bool bfs()
{
	memset(d,0,sizeof d);
	hh = 0,tt = -1;
	q[++tt] = s;d[s] = 1;now[s] = ver[s];
	while(hh <= tt)
	{
		int u = q[hh++];
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q[++tt] = v;
				now[v] = ver[v];
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int limit)
{
	if(u == t)	return limit;
	int flow = 0,k;
	for(int i = now[u];~i && flow < limit;i = succ[i])
	{
		now[u] = i;
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(limit - flow,cap[i]));
			if(!k)	d[v] = -1;
			cap[i] -= k;
			cap[i ^ 1] += k;
			flow += k;
		}
	}
	return flow;
}
void dfs(int u,int st[],int adj)
{
	st[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];int j = i ^ adj;
		if(cap[j] && !st[v])
		{
			st[v] = 1;
			dfs(v,st,adj);
		}
	}
}
int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d%d",&n,&m);
	s = 1;t = n;
	while(m--)
	{
		int u,v,c;scanf("%d%d%d",&u,&v,&c);
		++u;++v;
		add(u,v,c);
	}
	int flow = 0,maxflow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	dfs(s,st_s,0);
	dfs(t,st_t,1);
	int res = 0;
	for(int i = 0;i < idx;i += 2)
	{
		int v = edge[i],u = edge[i ^ 1];
		if(!cap[i] && st_s[u] && st_t[v])	
			++res;
	}
	printf("%d\n",res);
    return 0;
}